public class ReverseNodesInKGroup {
    public ListNode reverseKGroup(ListNode head, int k) {
        // 1.求出需要翻转的组数
        int group = size(head) / k;

        // 2.逆序长度为 k 的链表 group 次
        ListNode virtualNode = new ListNode();
        ListNode prev = virtualNode;
        ListNode cur = head;
        for(int i = 0; i < group; i++) {
            // 记录每组第一个节点位置, 方便后续连接各组链表
            ListNode tmp = cur;
            for(int j = 0; j < k; j++) {
                // 逆序每组元素(头插法)
                ListNode curNext = cur.next;
                cur.next = prev.next;
                prev.next = cur;
                cur = curNext;
            }
            // 用于连接各组的指针 prev 指向 tmp 位置
            prev = tmp;
        }

        // 将后续小于k的元素连接起来
        prev.next = cur;
        return virtualNode.next;
    }

    // 返回链表的长度
    public int size(ListNode head) {
        int size = 0;
        ListNode cur = head;
        while (cur != null) {
            size++;
            cur = cur.next;
        }
        return size;
    }
}
